//class Solution {
//public:
//    vector<int> ret;
//    vector<int> preorderTraversal(TreeNode* root) {
//        dfs(root);
//        return ret;
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr) return;
//        ret.push_back(root->val);
//        if (root->left) dfs(root->left);
//        if (root->right) dfs(root->right);
//    }
//};




class Solution {
public:
    class Comp
    {
    public:
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Comp> pq;
        for (auto& list : lists)
            if (list) pq.push(list);
        ListNode* newhead = new ListNode(0), * prev = newhead;
        while (!pq.empty())
        {
            ListNode* tmp = pq.top();
            pq.pop();

            prev->next = tmp;
            prev = prev->next;

            if (tmp->next)
                pq.push(tmp->next);
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};